package org.example.myleet.p652;

import org.example.myleet.Utils.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {

    private static final TreeNode DUMMY = new TreeNode(Integer.MIN_VALUE);

    private List<TreeNode> res;

    private Map<String, TreeNode> serializedMapNode;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        res = new ArrayList<>();
        serializedMapNode = new HashMap<>();
        dfs(root);
        return res;
    }

    private String dfs(TreeNode parent) {
        if (null == parent) {
            return "null";
        }
        String key = parent.val + "(" + dfs(parent.right) + "," + dfs(parent.left) + ")";
        TreeNode node = serializedMapNode.get(key);
        if (null == node) {
            serializedMapNode.put(key, parent);
        } else if (DUMMY != node) {
            res.add(node);
            serializedMapNode.put(key, DUMMY);
        }
        return key;
    }
}
